//给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。 
//
// 子数组 是数组的一段连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,0,1,0,1], goal = 2
//输出：4
//解释：
//有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,0,0,0], goal = 0
//输出：15
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 10⁴ 
// nums[i] 不是 0 就是 1 
// 0 <= goal <= nums.length 
// 
//
// Related Topics 数组 哈希表 前缀和 滑动窗口 👍 335 👎 0

package leetcode.editor.cn;

import java.sql.PreparedStatement;

//java:和相同的二元子数组
public class Q0930BinarySubarraysWithSum {
    public static void main(String[] args){
        Solution solution = new Q0930BinarySubarraysWithSum().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // 恰好型滑动窗口， >= k - >=k+1 就是k个的数量
        return numSubarraysThanSum(nums, goal) - numSubarraysThanSum(nums, goal + 1);
    }

    // 计算和>=k 的子数组个数
    public int numSubarraysThanSum(int[] nums, int k) {
        int n = nums.length, left = 0, res = 0;
        int subSum = 0;
        // 扩大有边界
        for (int right = 0; right < n; right++) {
            subSum += nums[right];
            // 满足情况，扩大左边界，找到满足情况的最短情况
            while (left <= right && subSum >= k) {
                subSum -= nums[left];
                left++;
            }
            // 越长越合法，以right结尾的，[0, left - 1]随便选
            res += left;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}